#ifndef __HEAP_H
#define __HEAP_H

using namespace std;

#include "constants.h"
#include <stdlib.h>
#include <iostream>


template <class E>
class Heap
{
  E* heap;
  int tail;
  int size;

 public:
  Heap();
  Heap(int);
  Heap(const Heap<E>&);
  void insert(E);
  E pop();
  E peak();
  int Size();
  int HasMore();
  void print();
  E operator[](int);
};

//Construct a heap of a default size
template <class E>
Heap<E>::Heap()
{
  heap = (E*)malloc(DEFSIZE*sizeof(E));
  tail = -1;
  size = DEFSIZE;
}


//Construct a heap of a given size
template <class E>
Heap<E>::Heap(int s)
{
  heap = (E*)malloc(s*sizeof(E));
  tail = -1;
  size = s;
}

//Copy constructor
template <class E>
Heap<E>::Heap(const Heap<E>& h)
{
  heap = (E*)malloc(h.size*sizeof(E));
  memcpy(heap, h.heap, h.size*sizeof(E));
  tail = h.tail;
  size = h.size;
}


//Insert an exchange into the heap
template <class E>
void Heap<E>::insert(E elem)
{
  int i = tail+1;

  // Can't insert into a full heap
  if (i == size - 1)
    return;

  while (i > 0 && heap[(i-1)/2] > elem)
    {
      heap[i] = heap[(i-1)/2];
      i = (i-1)/2;
    }
    heap[i] = elem;
    tail = tail + 1;
}

//Pop an exchange from the heap    
template <class E>
E Heap<E>::pop()
{
  E elem;
  if (tail < 0)
    {
      return elem;
    }
  else
    {
      elem = heap[0];
      heap[0] = heap[tail];
      tail = tail - 1;
      int i = 0;
      while (2*i+1 <= tail)
	{
	  int child = 2*i+1;
	  if ((child != tail) && (heap[child+1] < heap[child]))
	    child = child + 1;
	  if (heap[i] > heap[child])
	    {
	      E tmp = heap[child];
	      heap[child] = heap[i];
	      heap[i] = tmp;
	    }
	  else
	    break;		
	  i=child;
	}
      return elem;
    }
}


// Same as pop but do not remove an element from heap
template <class E>
E Heap<E>::peak()
{
  E elem;
  if (tail < 0)
    {
      return elem;
    }
  else
    {
      elem = heap[0];
       return elem;
    }
}

// Check if empty
template <class E>
int Heap<E>::HasMore()
{
  return tail > -1;
}


// Return element count
template <class E>
int Heap<E>::Size()
{
  return tail+1;
}
    
// Print heap
template <class E>
void Heap<E>::print()
{
  for (int i = 0; i <= tail; i++)
    cout << " position " << i << " elem " << heap[i] << "\n";
}

// Operator []
template <class E>
E Heap<E>::operator[](int index)
{
  return heap[index];
}

#endif
